{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Knight's Tour Code\n",
    "\n",
    "** Below is th ecode referenced in the video lecture. Please refer to the video lectures for full explanation.**"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def knightGraph(bdSize):\n",
    "    ktGraph = Graph()\n",
    "    for row in range(bdSize):\n",
    "        for col in range(bdSize):\n",
    "            nodeId = posToNodeId(row,col,bdSize)\n",
    "            newPositions = genLegalMoves(row,col,bdSize)\n",
    "            for e in newPositions:\n",
    "                nid = posToNodeId(e[0],e[1],bdSize)\n",
    "                ktGraph.addEdge(nodeId,nid)\n",
    "    return ktGraph\n",
    "\n",
    "def posToNodeId(row, column, board_size):\n",
    "    return (row * board_size) + column\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def genLegalMoves(x,y,bdSize):\n",
    "    newMoves = []\n",
    "    moveOffsets = [(-1,-2),(-1,2),(-2,-1),(-2,1),\n",
    "                   ( 1,-2),( 1,2),( 2,-1),( 2,1)]\n",
    "    for i in moveOffsets:\n",
    "        newX = x + i[0]\n",
    "        newY = y + i[1]\n",
    "        if legalCoord(newX,bdSize) and \\\n",
    "                        legalCoord(newY,bdSize):\n",
    "            newMoves.append((newX,newY))\n",
    "    return newMoves\n",
    "\n",
    "def legalCoord(x,bdSize):\n",
    "    if x >= 0 and x < bdSize:\n",
    "        return True\n",
    "    else:\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def knightTour(n,path,u,limit):\n",
    "        u.setColor('gray')\n",
    "        path.append(u)\n",
    "        if n < limit:\n",
    "            nbrList = list(u.getConnections())\n",
    "            i = 0\n",
    "            done = False\n",
    "            while i < len(nbrList) and not done:\n",
    "                if nbrList[i].getColor() == 'white':\n",
    "                    done = knightTour(n+1, path, nbrList[i], limit)\n",
    "                i = i + 1\n",
    "            if not done:  # prepare to backtrack\n",
    "                path.pop()\n",
    "                u.setColor('white')\n",
    "        else:\n",
    "            done = True\n",
    "        return done"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}
